The present invention relates to geographic data and more particularly the present invention relates to a way to represent a road network in a geographic database to facilitate certain navigation-related functions, such as route calculation.
Navigation systems provide useful features, such as calculating a route to a desired destination and providing guidance for following the route. In order to provide these features, navigation systems use geographic databases that include information about the locations of roads and intersections, estimated travel times along roads, the speed limits along roads, etc. Geographic databases used by navigation systems also include data about traffic restrictions, such as one-way streets, no-left-turns, etc., so that the navigation system can calculate a legal route (i.e., a route that conforms to applicable traffic laws and regulations). Using a geographic database, programming algorithms used in navigation systems can find an optimal (e.g, fastest or shortest) route to a specified destination.
A conventional way to represent roads in a geographic database is to represent them as discrete segments, i.e., wherein a segment corresponds to the portion of a road between intersections. In this kind of model, traffic restrictions (such as turn restrictions) are treated as properties of a road segment. This model conforms to the way roads are perceived and generally works well.
FIG. 1 is an illustration of a portion of a road network 10. FIG. 2 is a diagram that illutrates how the road network 10 shown in FIG. 1 is represented in a conventional geographic database 14.
In some geographic databases, a series of connected individual road segments are represented as an aggregation in order to facilitate some types of functions for which geographic databases are used. Examples of geographic databases in which a series of connected road segments are represented as an aggregation are disclosed in U.S. Pat. Nos. 6,038,559 and 6,112,200, the entire disclosures of which are represented by reference herein.
Although the conventional way of representing roads works well, there is room for improvement. For example, calculating a route using a geographic database can be computationally intensive. It would be beneficial if roads could be represented in a geographic database in a way that further facilitates certain functions, such as route calculation.
To address these and other objectives, an embodiment of the present invention comprises a method of representing a road network in a geographic database that facilitates determining routes between locations along the road network. In the geographic database, the road network is represented using transition point pair data. Each transition point pair data record indicates an entry point, an arm (or road segment) leading away from the entry point, an exit point, routing attributes, and possibly other data. Except for certain exceptions, such as multi-segment restricted driving maneuvers, the entry point and the exit point of a transition point pair are adjacent decision point intersections. A decision point intersection is an intersection at which a driver is required to make a decision which one of two or more possible road segments to take leading away from the intersection. The transition point pair data are used when calculating a route between two locations.